Skip to main content

例1

例1 BLO​

BLO

BB 城有 nn 个城镇，mm 条双向道路。每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。

你需要输出 nn 个整数，其中第 ii 个整数表示把与节点 ii 关联的所有边去掉之后 （不去掉节点 ii 本身），无向图中有多少个有序点对 (x,y)(x, y)，满足 xx 和 yy 不连通。

若 ii 不是割点，按照割点的定义，删掉点 ii 以后和与之相连的边以后，剩余的点依然保持连通，因此，只有点 ii 和其余点之间是不连通的，此时对答案的贡献为 2(n−1)2(n - 1)。

若 ii 是割点，ii 的子节点可以分为两类：

  • 满足 dfn[i]≤low[x]dfn[i] \le low[x] 的子节点
    这类节点在删掉 ii 出发的边以后，xx 的子树包含的节点将不再与其他节点连通。记这些节点为 s1,s2,⋯ ,sts_1, s_2, \cdots, s_t
  • 满足 dfn[i]≤low[x]dfn[i] \le low[x] 的子节点
    这类节点以及其子树包含的节点将与子树 s1,s2,⋯ ,sts_1, s_2, \cdots, s_t 以及 ii 之外的节点构成一个连通块。

总的来说，在 ii 是割点的条件下，删掉 ii 出发的边以后，节点会分为 t+2t + 2 个连通块，分别是子树 s1,s2,⋯ ,sts_1, s_2, \cdots, s_t 包含的节点，节点 ii，和剩余的节点。 那么，在一个连通块任选一个点，和不在该连通块的点都不连通。设子树 xx 的节点数量为 size[x]size[x]。

此时，对答案的贡献为：

∑k=1tsize[sk]⋅(n−size[sk])+1⋅(n−1)+(n−1−∑k=1tsize[sk])×(1+∑k=1tsize[sk])\displaystyle \sum_{k = 1}^{t} size[s_k] \cdot (n - size[s_k]) + 1 \cdot (n - 1) + (n - 1 - \sum_{k = 1}^{t} size[s_k]) \times (1 + \sum_{k = 1}^{t} size[s_k])

参考代码​

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 500010;
int head[N], ver[M * 2], Next[M * 2];
int dfn[N], low[N], Size[N];
long long ans[N];
bool cut[N];
int n, m, tot, num;

void add(int x, int y) {
    ver[++tot] = y; Next[tot] = head[x], head[x] = tot;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num; Size[x] = 1;
    int flag = 0, sum = 0;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            Size[x] += Size[y];
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                flag++;
                ans[x] += (long long)Size[y] * (n - Size[y]);
                sum += Size[y]; 
            } else low[x] = min(low[x], dfn[y]); 
        } else low[x] = min(low[x], dfn[y]);
    }
    
    if (x != 1 || flag > 1) cut[x] = true;
    
    if (cut[x])
        ans[x] += (long long)(n - sum - 1) * (sum + 1) + (n - 1);
    else
        ans[x] = 2 * (n - 1);
}

int main() {
    cin >> n >> m; tot = 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y); 
        if (x == y) continue;
        add(x, y); add(y, x);
    }
    tarjan(1);
    for (int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

上面参考代码中

if (cut[x]) ans[x] += (long long)(n - sum - 1) * (sum + 1) + (n - 1);
else ans[x] = 2 * (n - 1);

在 xx 不是割点的情况下，上面代码第一行中的 sum 自然为 00，依然等于 2(n−1)2(n - 1)。故代码可以省掉关于 xx 是否是割点的判断。